321C - Ciel the Commander - CodeForces Solution

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Thu, 09 Mar 2023 (04:29:26)
*
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n;
vector <int> adj[N];

bool vis[N];
int dp[N], b[N];

void dfs(int v, int p)
{
    dp[v] = 1;
    for (auto u: adj[v])
        if (u != p && !vis[u])
            dfs(u, v), dp[v] += dp[u];
    return;
}

int get(int v, int p, int sz)
{
    for (auto u: adj[v]) {
        if (u == p || vis[u])
            continue;
        if (dp[u] > sz / 2)
            return get(u, v, sz);
    }
    return v;
}

void cent(int v = 0, int p = -1)
{
    dfs(v, -1);
    v = get(v, -1, dp[v]);

    vis[v] = 1;
    if (p == -1)
        b[v] = 0;
    else
        b[v] = b[p] + 1;

    for (auto u: adj[v])
        if (!vis[u])
            cent(u, v);

    return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v, u--, v--;

        adj[u].push_back(v),
        adj[v].push_back(u);
    }

    cent();

    for (int i = 0; i < n; i++)
        cout << char('A' + b[i]) << ' ';

    return 0;
}